//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 
//
// 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "cbaebabacd", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
// 
//
// 示例 2: 
//
// 
//输入: s = "abab", p = "ab"
//输出: [0,1,2]
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length, p.length <= 3 * 10⁴ 
// s 和 p 仅包含小写字母 
// 
// Related Topics 哈希表 字符串 滑动窗口 👍 922 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class _438_FindAllAnagramsInAString {
    public static void main(String[] args) {
        Solution solution = new _438_FindAllAnagramsInAString().new Solution();
        String s = "abab";
        String p = "ab";
//        char[] a = s.toCharArray();
//        Arrays.sort(a);
//        System.out.println(a);
        System.out.println(solution.findAnagrams(s, p));
    }

    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            int sLen = s.length();
            int pLen = p.length();
            if (sLen < pLen) {
                return new ArrayList<>();
            }

            List<Integer> res = new ArrayList<>();
            int[] count = new int[26];
            for (int i = 0; i < pLen; i++) {
                count[s.charAt(i) - 'a']++;
                count[p.charAt(i) - 'a']--;
            }
            int differ = 0;
            for (int i = 0; i < 26; i++) {
                if (count[i] != 0) {
                    differ++;
                }
            }
            if (differ == 0) {
                res.add(0);
            }
            for (int i = 0; i < sLen - pLen; i++) {
                if (count[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                    --differ;
                } else if (count[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                    ++differ;
                }
                --count[s.charAt(i) - 'a'];

                if (count[s.charAt(i + pLen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                    --differ;
                } else if (count[s.charAt(i + pLen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                    ++differ;
                }
                ++count[s.charAt(i + pLen) - 'a'];

                if (differ == 0) {
                    res.add(i + 1);
                }
            }
            return res;
        }
    }

    /**
     * 官方解法，滑动窗口
     */
    class Solution2 {
        public List<Integer> findAnagrams(String s, String p) {
            int sLen = s.length();
            int pLen = p.length();
            if (sLen < pLen) {
                return new ArrayList<>();
            }
            List<Integer> ans = new ArrayList<>();
            int[] sCount = new int[26];
            int[] pCount = new int[26];
            for (int i = 0; i < pLen; i++) {
                ++sCount[s.charAt(i) - 'a'];
                ++pCount[p.charAt(i) - 'a'];
            }
            if (Arrays.equals(sCount, pCount)) {
                ans.add(0);
            }
            for (int i = 0; i < sLen - pLen; i++) {
                --sCount[s.charAt(i) - 'a'];
                ++sCount[s.charAt(i + pLen) - 'a'];

                if (Arrays.equals(sCount, pCount)) {
                    ans.add(i + 1);
                }
            }
            return ans;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 超时了
     */
    class Solution1 {
        public List<Integer> findAnagrams(String s, String p) {
            int len = p.length();
            List<Integer> res = new ArrayList<>();
//            HashMap<Character, Integer> map = new HashMap<>(p.length());
//            for (int i = 0; i < len; i++) {
//                map.put(p.charAt(i), map.getOrDefault(p.charAt(i), 0) + 1);
//            }
            char[] pp = p.toCharArray();
            Arrays.sort(pp);
            p = Arrays.toString(pp);
            for (int i = 0; i <= s.length() - len; i++) {
                char[] ss = s.substring(i, i + len).toCharArray();
                Arrays.sort(ss);
                String sss = Arrays.toString(ss);
                if (p.equals(sss)) {
                    res.add(i);
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}